1. Field of the Invention
The present invention generally relates to operations planning in a process industry and, more particularly, to a near-optimal inventory matching computer implemented method based on a multi-assignment backlifting procedure.
2. Background Description
Operations planning in a process industry typically begins with a order book which contains a list of orders that need to be satisfied. The initial two steps in an operations planning exercise involves (1) first trying to satisfy orders from the order book using leftover stock from the inventory and (2) subsequently designing manufacturing units for manufacture from the remaining orders. The present invention relates to the first step.
Two important characteristics of a process industry are that the products are manufactured based on the orders not based on a forecast of the expected demand (as in retail or semiconductor manufacturing) and, as a consequence, the inventory is merely the stock of previously produced units which for reasons of quality could not be shipped to the customer.
The first problem of applying orders against an existing inventory has a strong flavor of a matching problem--we call this the Inventory Matching Problem. An inventory of previously produced units could consist of units such as steel slabs in a steel industry or a roll of paper in the paper industry. There is of course wide variation across these units in terms of their weights, grade and surface quality all of which need to be accounted for in doing the match. Additional constraints arise in terms of the weight of the orders and the slabs against which they can be matched. There arise integrality constraints which further restricts the matches that are possible. Further, the number and type of orders that can be applied against a slab is constrained based on various manufacturing considerations. The goal of Inventory Matching is to maximize the total weight of the order book that is applied against the inventory. An additional goal is to minimize the unused weight of those slabs that are matched against orders. The present invention is a fast computer implemented method which provides near-optimal solutions to the Inventory Matching Problem.
3. Problem Description
The order book contains a list of orders that need to be delivered. Each order has a target weight (O.sub.t) that needs to be delivered. However, there are allowances with respect to this target weight which specify the minimum (O.sub.min) and maximum weight (O.sub.max) that are accepted at delivery. Over and above the total weight (per order) that needs to be delivered there are additional restrictions regarding the size and number of units into which this order can be factorized at delivery. For example, with each order is associated a range for the weight of the manufacturing units which are delivered. Let us assume that the minimum weight for the manufacturing unit is MU.sub.min and the maximum is MU.sub.max. Then for each order we need to deliver an integral number of manufacturing units (MU.sub.number) of size in the interval [MU.sub.min, MU.sub.max ] so that the total order weight delivered is in the range [O.sub.min, O.sub.max ]. In order to fulfill an order, we need to choose a size for the manufacturing unit (MU.sub.size) and the number of manufacturing units (MU.sub.number) to be produced such that EQU O.sub.min .ltoreq.MU.sub.size .times.MU.sub.number .ltoreq.O.sub.max MU.sub.min .ltoreq.MU.sub.size .ltoreq.MU.sub.max MU.sub.number .epsilon.{0,1,2, . . . } (1)
Notice that the MU.sub.number is a general integer variable. Additionally, the constraint represented by Equation (1) is a bilinear constraint.
In addition the weight requirements, each order has four other classes of attributes: (1) The first set pertains to the quality requirements such as grade, surface and internal properties of the material to be delivered. (2) The second set are physical attributes such as the width and thickness of the product delivered. (3) The third set of attributes refer to the finishing process that needs to be applied to the manufacturing units. For example, car manufacturers often require the steel sheets to be galvanized. (4) Finally the fourth set of attributes provide the maximum and the minimum slab size that can be used to produce this order. At first this might sound odd since the decision of how to manufacture slabs to fulfill an order should be left to a manufacturer. It turns out that the maximum and minimum allowable slab size is in fact determined by the manufacturer based on the current technological limitations of process technologies. For example, in a steel mill, all slabs need to be hot rolled to produce units of desired physical dimensions. However, based on the width and thickness required and the quality requirements, the maximum size of the slab that can be hot rolled is constrained, and this determines the allowable maximum allowable slab size. Similar considerations are used to prescribe the minimum allowable slab size.
Associated with each slab in the inventory are two sets of attributes: (1) The first attribute pertains (as in the case of orders) to quality requirements exactly as in the case of orders, and (2) the second case pertains to the physical dimensions of the slab such as the width, thickness and the weight of the slab.
The inventory matching problem requires that we maximize the total weight of applied orders while minimizing the unused portion of the applied slabs, subject to certain constraints that arise out of manufacturing considerations. In the following paragraphs we explain these constraints.
For a given order book, we first assign for each order a set applicable slabs from the inventory. In the general case when we have no restrictions, all slabs can be applied against an order. Let us represent this assignment using nodes for orders and slabs, and arcs to indicate orders and slabs which can be applied against each other. This leads to an undirected bipartite graph from orders to slabs (in the inventory). The graph is undirected because a slab j, applicable to an order i, implies that order i is applicable against slab j. Note that an equivalent representation of this bipartite graph is a matrix of orders as rows and slabs as columns. Each row (corresponding to an order) is a zero/one vector where the ones indicate the applicable slabs. Since the bipartite graph is undirected, this matrix is symmetric. We will consider the upper half of this symmetric matrix.
Two sets of constraints arise as a set of assignment restrictions in terms of the applicable slabs for each order. These assignment restrictions are based on quality and physical dimension considerations.
1. The first restriction is that for a given order only slabs which are of the same quality or higher quality can be applied. If we were to list the orders and slabs in terms of non-decreasing value of quality, then the quality restriction would lead to a staircase structure. Consider the zero/one row for each order; the quality of slabs is improved as we move from left to right. Therefore, once we find a slab of good enough quality, all subsequent slabs are applicable to this order. Therefore, quality restrictions might actually reduce the total number of applicable slabs for any order. PA0 2. The second set of restrictions arise from considerations of width and thickness of the orders and the slabs. Usually, the thickness and width of a slab can be altered using rolling; however, there is a corresponding range which identifies the limits based on machining or rolling considerations. For example, a slab of width S.sub.w and thickness S.sub.t can be rolled to a slab of width in the range .left brkt-bot.S.sub.w.sup.min, S.sub.w.sup.max .right brkt-bot. and thickness in the range .left brkt-bot.S.sub.t.sup.min, S.sub.t.sup.max .right brkt-bot.. As long as the order width and thickness requirements fall into this range, the order can be applied against the slab. These consideration further restrict the number of slabs that can be assigned against an order. Notice that this additional restriction does not affect the staircase structure but only makes it sparse. PA0 Problem Constraints: ##EQU1## Problem Objectives: Maximize applied weight. ##EQU2## Minimize surplus weight: A unused is accounted for slab j only if we use the slab. ##EQU3## PA0 Pruning: If the relaxed problem has a solution that is worse than the current best feasible objective value, prune the node. PA0 Updating: Update the integer solution if the solution is such that for each edge the MU.sub.size and the MU.sub.number satisfy the constraints described in Equation (1). PA0 Branching: Branch on some edge in the bipartite graph if the relaxed solution does not satisfy the restrictions in Equation (1) and if its objective value is better than the current best feasible solution. PA0 1. The first shortcoming of such an approach is that there is no guarantee of convergence. Therefore, often for large problems (with over a few hundred edges) the branch-and-bound approach is not able to find feasible solutions/matching. PA0 2. Because of incremental approach to searching the space of matches, the speed of this algorithm depends critically on how close the actual optimal solution is to the relaxed solution generated by the linear program. For the inventory matching problem, both the integrality constraints on the MU.sub.number and the color constraints render the relaxed problem to be a rather loose approximation to the actual problem. Hence, the branch-and-bound algorithm is very slow (a couple of hours) for even moderate sized (less than 100 edges) problems. Such a response time is not acceptable in real world situations where the entire production plan (of which the inventory matching is a small part) has to be done within a couple of hours. PA0 3. Finally, the branch-and-bound algorithm can optimize for only one objective at a time. The Inventory Matching Problem has two major competing objectives--maximize applied quantity and minimize partial surplus. In order to solve for both these objectives, the algorithm has to be applied once for each objective by constraining the other objective at some desirable goal. This procedure is repeated until no further improvement in both objectives can be achieved. Since the algorithm response for each objective is slow, such a goal programming approach is too slow for real world applications. PA0 1. The inventory problem can be represented as a list of applicable matches, M.sub.L. Each element M.sub.i of the list M.sub.L corresponds to an edge in the bipartite graph and hold pointers to a unique order O.sub.i and a slab S.sub.i which can be applied against each other. PA0 2. Another representation for this problem is using a list of orders, O.sub.L. Each element O.sub.i of list O.sub.L is an order (from the order book) and has associated with it a list of applicable matches from M.sub.L. These applicable matches for O.sub.i can be used to identify the corresponding slabs applicable to it. PA0 3. The last representation consists of a list of slabs S.sub.L available in the inventory. Each element S.sub.i of S.sub.L is a slab and associated with it a list of applicable matches from M.sub.L. These applicable matches for S.sub.i can be used to identify the corresponding orders applicable against it. PA0 1. A solution constitutes of an applied match list AM.sub.L. Each element AM.sub.i also belongs to the list M.sub.L but has associated with it a value for MU.sub.number and MU.sub.size. Therefore, a solution can be represented by a subset of M.sub.L with associated assignments. PA0 2. Another representation consists of an applied order list AO.sub.L. Each element AO.sub.i also belongs to the list O.sub.L and has associated with it a list of applied matches. PA0 3. Finally, the solution is also represented using a list of applied slabs AS.sub.L. Each element AS.sub.i also belongs to the list S.sub.L and has associated to it a list of applied matches.
After incorporating these two restrictions, the order applicability matrix becomes quite sparse, usually about 5% of the entries are non-zero. As a result, these restrictions lead to a more generalized version of the multiple knapsack problem where the assignment restrictions can be specified as a bipartite graph. The conventional multiple knapsack is an instance of this general problem with a complete bipartite graph. The problem that we have outlined so far with the two restrictions outlined above presents another instance with a sparse staircase structure.
The final set of constraints pertain to packing multiple orders on a slab. The assignment restrictions specify a list of orders that can be applied against any slab in the inventory. However, not all orders assignable to a slab can be packed together on the slab. Such packing constraints emerge out of process considerations in the hot and cold mill and the finishing line. Consider a schematic diagram of the route of a slab through a steel mill as shown in FIG. 1.
A slab 10 is sent through a hot strip mill 11 to produce a hot coil 12. The hot coil 12 may be sent through a cold mill 13 (if required) and subsequently to the finishing line 14. After the hot/cold mill, the slab is in form of a sheet or a coil. Before the coils are sent to the finishing line, they are cut according to different order specifications. Since orders with different requirements for the finishing line are cut from the slab before processing, it is possible to pack orders on the same slab. However, cutting coils is time consuming and cumbersome and, most important, the cutting machine is often the bottleneck in the process flow. Hence, often strong constraints are posed in terms of the number of cuts per slab that are allowed based on the current state of the cutting machine. The simplest representation of this constraint is to specify a limit on the number of cuts or the number of different order types (i.e., orders that need to be separated before the finishing line).
In order to represent this constraint more formally, we introduce a color attribute for each order which describes the set of finishing operations required. Orders which require the same set of finishing operations are considered to be of the same type (and hence the same color) and they do not need to be separated before the finishing line. Orders that require different operations in the finishing line are of different type (and hence of different color) have to be separated before the finishing line. Associating a color with each order based on the finishing operations, we can specify a constraint in terms of a limit on the number of different colored orders that are allowed on the same slab. We refer to these process based constraints as the color constraints.